/*
 * 3.2
 * How would you design a stack which, in addition to push and pop, also has a function
 * min which returns the minimum element? Push, pop and min should all operate in
 * O(1) time.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _node_t {
    int v;
    struct _node_t *prev;
} node_t;

node_t *new_node(int v)
{
    node_t *node = (node_t *)malloc(sizeof(node_t));
    memset(node, 0, sizeof(node_t));
    node->v = v;
    return node;
}

/* keep a min list */
class istack
{
public:
    istack() : top(NULL), min_list(NULL) {
    }
    ~istack() {
        node_t *curr, *prev = top;
        while (prev) {
            curr = prev->prev;
            free(prev);
            prev = curr;
        }
        prev = min_list;
        while (prev) {
            curr = prev->prev;
            free(prev);
            prev = curr;
        }
    }
    void push(int v) {
        node_t *t = new_node(v);
        t->prev = top;
        top = t;
        if (!min_list || v <= min_list->v) {
            t = new_node(v);
            t->prev = min_list;
            min_list = t;
        }
    }
    int pop() {
        if (!top) {
            return -1;
        }
        node_t *t;
        int v = top->v;
        t = top;
        top = top->prev;
        free(t);
        if (v == min_list->v) {
            t = min_list;
            min_list = min_list->prev;
            free(t);
        }
        return v;
    }
    int min() {
        if (!min_list) {
            return -1;
        }
        return min_list->v;
    }
private:
    node_t *top;
    node_t *min_list;
};

int main()
{
    istack s;
    s.push(3);
    s.push(2);
    s.push(6);
    s.push(1);
    s.push(4);
    printf("min=%d\n", s.min());
    s.pop();
    printf("min=%d\n", s.min());
    s.pop();
    printf("min=%d\n", s.min());
    s.pop();
    printf("min=%d\n", s.min());
    s.pop();
    printf("min=%d\n", s.min());
    return 0;
}
